package com.fwpsl.graph.shortestpath.singlesource;

import com.fwpsl.graph.Edge;
import com.fwpsl.graph.Graph;
import com.fwpsl.graph.Vertex;

import java.util.*;
import java.util.stream.Collectors;

import static com.fwpsl.graph.shortestpath.singlesource.AbstractSingleSource.PathNode.PATH_NODE_TYPE_SINGLE;

/**
 * @author: 风戏fw
 * @date: 2024/4/14
 * @description: Bellman-Ford：求解单源最短路径问题的一种算法。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。
 * 其优于Dijkstra算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。但算法可以进行若干种优化，提高了效率。
 * 时间复杂度：O(VE)
 */
public class BellmanFord<T> extends AbstractSingleSource<T> {

    /**
     * Bellman-Ford算法
     * 松弛：每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短。
     * 由于图的最短路径最长不会经过超过条边，所以可知贝尔曼-福特算法所得为最短路径。
     * <p>
     * 负边权操作：与Dijkstra算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，
     * 这就确定了Bellman-Ford算法可以对负边进行操作而不会影响结果。
     * <p>
     * 负权环判定：因为负权环可以无限制的降低总花费，所以如果发现第n次操作仍可降低花销，就一定存在负权环。
     *
     * @param graph
     * @param start
     * @return
     */
    @Override
    public Map<Vertex<T>, PathNode> singlePathList(Graph<T> graph, Vertex<T> start) {
        // 距离数组
        Map<Vertex<T>, PathNode> distMap = new HashMap<>();
        for (Vertex<T> vertex : graph.getVertices()) {
            distMap.put(vertex, new PathNode(vertex, INF, PATH_NODE_TYPE_SINGLE));
        }
        distMap.get(start).distance = 0;

        // 放松所有边
        List<Edge<T>> edges = graph.getEdges();
        for (int i = 1; i < graph.getVertexNum(); i++) {
            for (Edge<T> edge : edges) {
                Vertex<T> source = edge.getSource();
                Vertex<T> destination = edge.getDestination();
                Double newDist;
                if ((newDist = distMap.get(source).distance + edge.getWeight()) < distMap.get(destination).distance) {
                    distMap.get(destination).distance = newDist.intValue();
                    distMap.get(destination).preVertex = source;
                }
            }
        }

        for (Edge<T> edge : edges) {
            if ((distMap.get(edge.getSource()).distance + edge.getWeight()) < distMap.get(edge.getDestination()).distance) {
                System.out.println("图中包含负权重环");
                return null;
            }
        }

        return distMap;
    }

    /**
     * 仅返回最短路径
     *
     * @param graph
     * @param vertex
     * @return
     */
    public Map<Vertex<T>, Integer> distMap(Graph<T> graph, Vertex<T> vertex) {
        Map<Vertex<T>, PathNode> distMap = singlePathList(graph, vertex);
        if (distMap == null) {
            return null;
        }

        return distMap.entrySet().stream().collect(Collectors.toMap(e -> e.getKey(), e -> e.getValue().distance));
    }

    public static void main(String args[]) {
        Graph<Integer> graph = new Graph<>();
        graph.addEdge(0, 1, -1);
        graph.addEdge(0, 2, 4);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3, 2);
        graph.addEdge(1, 4, 2);
        graph.addEdge(3, 2, 5);
        graph.addEdge(3, 1, 1);
        // 情况1：包含权重为0的环
        graph.addEdge(4, 3, -3);
        // 情况2：包含负权重的环
//        graph.addEdge(4, 3, -5);

        BellmanFord<Integer> bf = new BellmanFord<>();

        Integer start = 0, end = 3;
        bf.testSinglePathList(graph, start, end);

        start = 0;
        end = 2;
        bf.testSinglePathList(graph, start, end);

        start = 3;
        end = 2;
        bf.testSinglePathList(graph, start, end);
    }
}
